1. Field of the Invention
The present invention relates to a Steiner tree handling device, Steiner tree handling method, and Steiner tree handling program which are capable of providing algorithm for executing deformation of a given Steiner tree, determining a range where the Steiner tree can exist, and obtaining the number of variations on the Steiner tree based on the deformation.
2. Description of the Related Art
Conventionally, the Steiner tree has been widely used to solve problems in wirings in layout designs of LSI. Those designs are represented by prediction of the wiring length or wiring route of a network, route determination in a global wiring, and the like. In the creation algorithm of the Steiner tree, one Steiner tree is created with its edges weighted and with its total cost minimized. Actually, however, there are plural Steiner trees each of which has the minimum cost. This feature is called flexibility. A method focused on a flip of the Steiner tree has been proposed as a method of obtaining a Steiner tree which fits the purpose of design among the plural Steiner trees existing with the minimum cost (for example, see Non-Patent literatures 1 and 2).
The flip means a case that there is no Steiner point on edges between two points that do not exist on the same horizontal or vertical line and connection to either upper-L or lower-L is possible. According to the method of Hu described in the non-patent literature 1, an edge which can be flipped is defined as a soft edge, and fixture of the edge is extended later.
According to the method of Bozorgzadeh et al. described in the non-patent literature 2, deformation is executed on a given Steiner tree to maximize the part which can be flipped. Thus, the flexibility of the flip of the Steiner tree is used to obtain a Steiner tree which fits the purpose of design, so that this method is very effective.
The deformation of the Steiner tree without using a flip, as described above, has been applied to insertion of a repeater avoiding a blockage (for example, see non-patent literature 3). In the method of this Alpert, the path of the Steiner tree is deleted with respect to the Steiner tree created regardless of a blockage, and a route is newly searched for in a maze routing method, to achieve deformation. In this case, the Steiner tree to be given first is a guide. Based on this guide, the Steiner tree is deformed to comply with the purpose of the insertion of a repeater.
Thus, the flexibility of the Steiner tree is a widely applicable property. Conventionally, the number of variations on the Steiner tree is obtained by deformation using the flexibility of the Steiner tree, and estimation of the wire property (e.g., estimation of wire congestion degree) has been achieved. This wire property estimation means that, before actually providing wires, a wiring area is divided into small areas. With respect to each small area, the congestion degree comparing an actual wiring quantity with a wiring-tolerance capacitance indicative of tolerable wiring is calculated to show wiring possibility.
The importance of the wire property estimation lies in that estimation is carried out in the stage of arranging elements and an index for improving the layout is provided to enable wirings. If it is determined that wiring is possible according to a wire property estimation, it is necessary to guarantee that wiring is possible up to details of wires.
Three typical methods of wire property estimation (e.g., wire congestion degree estimation) are known, that is, an experimental method, a probabilistic method, and a global wiring method.
Known experimental method (see non-patent literatures 4 and 5) is a method based on a bounding box. Also known is a method using the Rent's rule (see non-patent literature 6).
Known probabilistic methods are those of Hou and Lou (see non-patent literatures 7 and 8).
Known global wiring methods are those of Parakh et al. and Wang et al. (see non-patent literatures 9 and 10).
Non-Patent Literature 1:
J. Hu, S. Sapatnekar, “A Timing-constrained Algorithm for Simultaneous Global Routing of Multiple Nets”, Proc. ICCAD, 2000
Non-Patent Literature 2:
E. Bozorgzadeh, Ryan Kastner, Majid Sarrafzadeh, “Creating and Exploiting Flexibility in Steiner Trees”, Proc. DAC, 2001
Non-Patent Literature 3:
C. J. Alpert, G. Gandham, et al, “Steiner Tree Optimization for Buffers, Blockages, and Bays”, IEEE TCAD vol. 20, No. 4, 2001
Non-Patent Literature 4:
M. Wang and M. Sarrafzadeh, “Behavior of Congestion Minimization During Placement”, Proc. ISPD, 1999
Non-Patent Literature 5:
C. E. Cheng, “RISA: Accurate and Efficient Placement Routability Modeling”, Proc. ICCAD, 1994
Non-Patent Literature 6:
X. Yang, R. Kastner, and M. Sarrafzadeh, “Congestion Estimation During Top-down Placement”, IEEE Transactions on Computer-Aided Design, Vol. 21, No. 1, 2002
Non-Patent Literature 7:
W. Hou, H. Yu and W. H. Kao, “A New Congestion-Driven Placement Algorithm Based on Cell Inflation”, Proc. ASPDAC, 2001
Non-Patent Literature 8:
J. Lou, S. Thakur, et al., “Estimating Routing Congestion Using Probabilistic Analysis”, IEEE Transactions on Computer-Aided Design, Vol. 21, No. 1, 2002
Non-Patent Literature 9:
P. N. Parakh, R. B. Brown and K. A. Sakallah, “Congestion Driven Quadratic Placement”, Proc. DAC, 1998
Non-Patent Literature 10:
M. Wang and M. Sarrafzadeh, “Modeling and Minimization of Routing Congestion”, Proc. ASPDAC, 2000
However, with respect to the methods suggested in the above non-patent literatures 1 to 3, it has been demanded that the range where a Steiner tree exists and the variations on the Steiner tree due to deformation of the Steiner tree are obtained by more effectively using the flexibility of the Steiner tree to achieve more realistic deformation.
In addition, the methods for wire congestion estimation suggested in the above non-patent literatures 4 to 10 involve the following problems:
In the method according to the non-patent literature 4, which uses a bounding box, the simplest model is a method of assuming the half of the peripheral length of the bounding box to be the wiring route, but this model is not practical.
In the method of RISA introduced in the non-patent literature 5, the probability at which a wiring passes a location in a bounding box is obtained based on a wire distribution map created from plural Steiner trees. In this method, the area where wires pass is set within the range of the bounding box, with respect to one net. Further, the possibility that a wire passes a location (x, y) in the range is obtained as a wire distribution map, by changing the number of pins and generating Steiner trees with respect to a plurality of sets obtained with the plural pins located at random for every pin number. The method according to the non-patent literature 6 utilizes a point that the wiring length can be estimated from the Rent's rule.
In these experimental methods, wires are assumed, to some extent, to be provided on even routes where wires do not actually pass. The wire congestion degree estimation does not achieve high precision.
In the method of Hou suggested in the non-patent literature 7 as a probabilistic method, the probability is based on the following prerequisites. That is, a star-model in which each pin is connected from the center of a pin location on a net is used, and either Lower-L or upper-L is used between two pins in actual wiring. In the method of Lou suggested in the non-patent literature 8, a pair of two pins is created based on creation of a Steiner tree, and probabilistic estimation is obtained from all the numbers of routes between the paired two pins.
In these probabilistic methods, the congestion degree between two pins can be calculated including plural bent portions. However, there is a problem that estimation depends on a created Steiner tree because the star and Steiner tree which decide the shape of the net are each one single form.
In estimation of the wire congestion degree according to the methods of Parakh et al. suggested in the non-patent literature 9 and of Wang et al. suggested in the non-patent literature 10 as methods based on global wiring, the precision is high when using the same global wiring as that used in estimation of actual wiring. In these methods, however, the estimation generally tends to depend on the capability of the global wiring engine. There is also a problem that the estimation results differ depending on the capability of global wires used.
The present invention has been made in view of the problems described above and its object is to provide a handling device for a Steiner tree, a handling method thereof, and a handling program thereof, which can deform a Steiner tree with use of flexibility of the Steiner tree, can hence obtain a range where the Steiner tree can exist or obtain the number of variations on the Steiner tree, and can further estimate the wire congestion degree with high precision by using the results obtained.